package com.LeeCode;

/**
 * 具有所有最深节点的最小子树
 */

public class Code865 {
    public static void main(String[] args) {
        Integer[] arr = {3, 5, 1, 6, 2, 0, 8, null, null, 7, 4};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code865().subtreeWithAllDeepest(root).val);
    }


    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).node;
    }

    private Result dfs(TreeNode node) {
        if (node == null) {
            return new Result(null, 0);
        }

        Result left = dfs(node.left);
        Result right = dfs(node.right);

        // 左右子树深度相同，则当前节点可能是答案
        if (left.depth == right.depth) {
            return new Result(node, left.depth + 1);
        }
        // 否则取更深的一边作为结果
        else if (left.depth > right.depth) {
            return new Result(left.node, left.depth + 1);
        } else {
            return new Result(right.node, right.depth + 1);
        }
    }

    // 辅助类：保存当前子树的最深节点 和 深度
    private class Result {
        TreeNode node;
        int depth;

        Result(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

}
